#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits == "") {
            return result;
        }

        result = vector<string>();
        this->findCombination(digits, 0, "");
        return result;
    }
private:
    const string letterMap[10] = {
        " ", 
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    void findCombination(const string &digits, int index, const string &s) 
    {
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }
        char c = digits[index];
        string letters = letterMap[c-'0'];
        for (int i = 0; i < letters.size(); i++) {
            findCombination(digits, index + 1, s + letters[i]);
        }
    }
    vector<string> result;
};


int main(int argc, char *argv[])
{
    Solution s;
    
    cout << "23: " << endl;
        
    vector<string> res = s.letterCombinations("234");

    for (int i = 0; i < res.size(); i ++) {
        cout << i << ": " << res[i] << endl;
    }

    return 0;
}
